// 中序遍历（DFS - 深度优先）

// 方法一：递归实现
function inorderTraversal(root) {
  const result = [];

  function traverse(node) {
    if (!node) return;
    traverse(node.left);    // 左
    result.push(node.val);  // 根
    traverse(node.right);   // 右
  }

  traverse(root);
  return result;
}


// 方法二：迭代实现（使用栈）
function inorderTraversalIterative(root) {
  const result = [];
  const stack = [];
  let current = root;

  while (current || stack.length) {
    // 深入左子树
    while (current) {
      stack.push(current);
      current = current.left;
    }

    // 回溯到父节点
    current = stack.pop();
    result.push(current.val);

    // 转向右子树
    current = current.right;
  }

  return result;
}